﻿#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
struct TreeNode
{
	TreeNode(const K& key,const V& val)
		:_val(val),
		_key(key),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr)
	{}

	bool is_leaf()
	{
		if (_left || _right)
			return false;

		return true;
	}

	K _key;
	V _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode* _parent;
};

template<class K,class V>
class BSTree
{
public:
	typedef TreeNode<K, V> Node;

	BSTree()
		:_root(nullptr)
	{}

	~BSTree()
	{
		_Destroy(_root);
	}

	bool insert(const K& key, const V& val)
	{
		Node* ins = new Node(key, val);

		return _insert(_root, ins);
	}

	Node* find(const K& key)
	{
		return _find(_root, key);
	}

	void erase(const K& key)
	{
		Node* erasement = find(key);
		_erase(erasement);
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

private:
	Node* _root;

	void _Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

	bool _insert(Node*& root,Node* ins)
	{
		if (root == nullptr)
		{
			root = ins;
			return true;
		}

		if (root->_key == ins->_key)
		{
			return false;
		}
		else if (root->_key > ins->_key)
		{
			ins->_parent = root;
			return _insert(root->_left, ins);
		}
		else if (root->_key < ins->_key)
		{
			ins->_parent = root;
			return _insert(root->_right, ins);
		}

	}

	Node* _find(Node* root,const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_key == key)
		{
			return root;
		}
		else if (root->_key > key)
		{
			return _find(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _find(root->_right, key);
		}
	}

	Node* _find_max(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_right == nullptr)
			return root;

		return _find_max(root->_right);
	}

	Node* _find_min(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_left == nullptr)
			return root;

		return _find_min(root->_left);
	}

	void _erase(Node* erasement)
	{
		if (erasement == nullptr)
			return;

		if (erasement->is_leaf())
		{
			if (!erasement->_parent)
				_root = nullptr;
			else if (erasement->_parent->_left == erasement)
				erasement->_parent->_left = nullptr;
			else if (erasement->_parent->_right == erasement)
				erasement->_parent->_right = nullptr;
			delete erasement;
			erasement = nullptr;
		}
		else if (erasement->_left == nullptr && erasement->_right)
		{
			if (!erasement->_parent)
			{
				_root = erasement->_right;
				_root->_parent = nullptr;
			}
			else if (erasement->_parent->_left == erasement)
			{
				erasement->_parent->_left = erasement->_right;
				erasement->_right->_parent = erasement->_parent;
			}
			else if (erasement->_parent->_right == erasement)
			{
				erasement->_parent->_right = erasement->_right;
				erasement->_right->_parent = erasement->_parent;
			}
			delete erasement;
			erasement = nullptr;
		}
		else if (erasement->_left && erasement->_right == nullptr)
		{
			if (!erasement->_parent)
			{
				_root = erasement->_left;
				_root->_parent = nullptr;
			}
			else if (erasement->_parent->_left == erasement)
			{
				erasement->_parent->_left = erasement->_left;
				erasement->_left->_parent = erasement->_parent;
			}
			else if (erasement->_parent->_right == erasement)
			{
				erasement->_parent->_right = erasement->_left;
				erasement->_left->_parent = erasement->_parent;
			}
			delete erasement;
			erasement = nullptr;
		}
		else
		{
			Node* tmp = _find_max(erasement->_left);
			erasement->_key = tmp->_key;
			_erase(tmp);
		}
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_key << ' ';
		_Inorder(root->_right);
	}

	size_t Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		size_t left = Height(root->_left);
		size_t right = Height(root->_right);

		return Max(left, right) + 1;
	}

	
};
